πŸ‘©β€πŸ’» 2579. 계단 였λ₯΄κΈ°

@Seongukbaek Posted March 24, 2022 Β· Updated March 24, 2022 Β· 5 min read

문제

계단 였λ₯΄κΈ° κ²Œμž„μ€ 계단 μ•„λž˜ μ‹œμž‘μ λΆ€ν„° 계단 κΌ­λŒ€κΈ°μ— μœ„μΉ˜ν•œ λ„μ°©μ κΉŒμ§€ κ°€λŠ” κ²Œμž„μ΄λ‹€. μ•„λž˜μ™€ 같이 각각의 κ³„λ‹¨μ—λŠ” μΌμ •ν•œ μ μˆ˜κ°€ μ“°μ—¬ μžˆλŠ”λ° 계단을 밟으면 κ·Έ 계단에 μ“°μ—¬ μžˆλŠ” 점수λ₯Ό μ–»κ²Œ λœλ‹€.

예λ₯Ό λ“€μ–΄ μ•„λž˜μ™€ 같이 μ‹œμž‘μ μ—μ„œλΆ€ν„° 첫 번째, 두 번째, λ„€ 번째, μ—¬μ„― 번째 계단을 λ°Ÿμ•„ 도착점에 λ„λ‹¬ν•˜λ©΄ 총 μ μˆ˜λŠ” 10 + 20 + 25 + 20 = 75점이 λœλ‹€.

계단 였λ₯΄λŠ” λ°λŠ” λ‹€μŒκ³Ό 같은 κ·œμΉ™μ΄ μžˆλ‹€.

  1. 계단은 ν•œ λ²ˆμ— ν•œ 계단씩 λ˜λŠ” 두 계단씩 였λ₯Ό 수 μžˆλ‹€. 즉, ν•œ 계단을 λ°ŸμœΌλ©΄μ„œ μ΄μ–΄μ„œ λ‹€μŒ κ³„λ‹¨μ΄λ‚˜, λ‹€μŒ λ‹€μŒ κ³„λ‹¨μœΌλ‘œ 였λ₯Ό 수 μžˆλ‹€.
  2. μ—°μ†λœ μ„Έ 개의 계단을 λͺ¨λ‘ λ°Ÿμ•„μ„œλŠ” μ•ˆ λœλ‹€. 단, μ‹œμž‘μ μ€ 계단에 ν¬ν•¨λ˜μ§€ μ•ŠλŠ”λ‹€.
  3. λ§ˆμ§€λ§‰ 도착 계단은 λ°˜λ“œμ‹œ λ°Ÿμ•„μ•Ό ν•œλ‹€.

λ”°λΌμ„œ 첫 번째 계단을 밟고 이어 두 번째 κ³„λ‹¨μ΄λ‚˜, μ„Έ 번째 κ³„λ‹¨μœΌλ‘œ 였λ₯Ό 수 μžˆλ‹€. ν•˜μ§€λ§Œ, 첫 번째 계단을 밟고 이어 λ„€ 번째 κ³„λ‹¨μœΌλ‘œ μ˜¬λΌκ°€κ±°λ‚˜, 첫 번째, 두 번째, μ„Έ 번째 계단을 μ—°μ†ν•΄μ„œ λͺ¨λ‘ λ°Ÿμ„ μˆ˜λŠ” μ—†λ‹€.

각 계단에 μ“°μ—¬ μžˆλŠ” μ μˆ˜κ°€ μ£Όμ–΄μ§ˆ λ•Œ 이 κ²Œμž„μ—μ„œ 얻을 수 μžˆλŠ” 총 점수의 μ΅œλŒ“κ°’μ„ κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

μž…λ ₯

  • μž…λ ₯의 첫째 쀄에 κ³„λ‹¨μ˜ κ°œμˆ˜κ°€ μ£Όμ–΄μ§„λ‹€.
  • λ‘˜μ§Έ 쀄뢀터 ν•œ 쀄에 ν•˜λ‚˜μ”© 제일 μ•„λž˜μ— 놓인 계단뢀터 μˆœμ„œλŒ€λ‘œ 각 계단에 μ“°μ—¬ μžˆλŠ” μ μˆ˜κ°€ μ£Όμ–΄μ§„λ‹€. κ³„λ‹¨μ˜ κ°œμˆ˜λŠ” 300μ΄ν•˜μ˜ μžμ—°μˆ˜μ΄κ³ , 계단에 μ“°μ—¬ μžˆλŠ” μ μˆ˜λŠ” 10,000μ΄ν•˜μ˜ μžμ—°μˆ˜μ΄λ‹€.

좜λ ₯

  • 첫째 쀄에 계단 였λ₯΄κΈ° κ²Œμž„μ—μ„œ 얻을 수 μžˆλŠ” 총 점수의 μ΅œλŒ“κ°’μ„ 좜λ ₯ν•œλ‹€.

πŸ“ Logic

static int climbStairs() {...}
  • dp[x][0] 은 xμΈ΅ κ³„λ‹¨κΉŒμ§€ κ°€λŠ”λ° μ—°μ†λœ 계단이 1개인 경우의 μ΅œλŒ€ 점수이고, dp[x][1] 은 μ—°μ†λœ 계단이 2개인 경우의 μ΅œλŒ€ μ μˆ˜μ΄λ‹€.
  • BOTTOM UPλ°©μ‹μœΌλ‘œ λͺ¨λ“  계단에 λŒ€ν•œ μ΅œλŒ€ 점수λ₯Ό κ΅¬ν•œ 이후, λ§ˆμ§€λ§‰ κ³„λ‹¨μ—μ„œ 두 경우 쀑 μ΅œλŒ“κ°’μ„ λ°˜ν™˜ν•œλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int[] costs; static int[][] dp; static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); costs = new int[N]; dp = new int[N][2]; for (int i = 0; i < N; i++) costs[i] = Integer.parseInt(br.readLine()); System.out.println(climbStairs()); br.close(); } static int climbStairs() { if (N == 1) return costs[0]; dp[0][0] = dp[0][1] = costs[0]; dp[1][0] = costs[1]; dp[1][1] = dp[0][0] + costs[1]; for (int i = 2; i < N; i++) { dp[i][0] = Math.max(dp[i - 2][0], dp[i - 2][1]) + costs[i]; dp[i][1] = Math.max(dp[i - 1][0], dp[i - 2][1]) + costs[i]; } return Math.max(dp[N - 1][0], dp[N - 1][1]); } }

✏️ Review

  • μ˜ˆμ „μ— C++둜 ν’€λ €λ‹€κ°€ λͺ» ν’€μ–΄μ„œ ν¬κΈ°ν–ˆλ˜ λ¬Έμ œμ˜€λ‹€. 이번 ν•™κΈ° κ³ λ¬Έν•΄ μ‹œκ°„μ— DP κ³Όμ œμ—μ„œ 이 λ¬Έμ œλ³΄λ‹€ 쑰건이 더 적은 문제λ₯Ό λ§Œλ‚˜μ„œ, 과제λ₯Ό ν•΄κ²°ν•œ 이후 λ‹€μ‹œ ν’€μ–΄λ³΄μ•˜λ‹€.
  • "μ—°μ†λœ μ„Έ 개의 계단을 λ°Ÿμ•„μ„  μ•ˆλœλ‹€"λŠ” 쑰건 λ•Œλ¬Έμ— κ³ λ―Όν–ˆκ³ , dp[][0] , dp[][1] 을 μ΄μš©ν•΄μ„œ ν•΄λ‹Ή κ³„λ‹¨κΉŒμ§€ μ—°μ†λœ 계단이 1개인 κ²½μš°μ™€ 2개인 경우λ₯Ό λ‚˜λˆ„μ–΄ κ΅¬ν˜„ν–ˆλ‹€.
  • DPλŠ” 싀버인데도 꼬이면 머리가 λ„ˆλ¬΄ μ•„ν”„λ‹€.

πŸ“• 좜처

https://www.acmicpc.net/problem/2579

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€